#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=188 lang=cpp
 *
 * [188] 买卖股票的最佳时机 IV
 */

// @lc code=start
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() < 2 || k < 1) return 0;
        vector<vector<int>> dp(2, vector<int>(k + 1, INT_MIN));
        int sz = prices.size();
        for (int i = 0; i < sz; i++) {
            dp[1][0] = max(dp[1][0], -prices[i]);
            for (int j = 1; j <= k; j++) {
                dp[0][j] = max(dp[0][j], dp[1][j - 1] + prices[i]);
                dp[1][j] = max(dp[1][j], dp[0][j] - prices[i]);
            }
        }
        return dp[0][k];
    }
};
// @lc code=end

